package com.algorithm.lesson_04;

import java.util.Stack;

/**
 * 用递归实现一个栈的逆序操作
 * 
 * @author Administrator
 *
 */
public class ReverseStackByRecursive {

	/**
	 * 得到一个栈的栈底元素，并将其移除
	 * 
	 * @param stack
	 * @return
	 */
	public static <T> T getAndRemoveLast(Stack<T> stack) {
		T result = stack.pop();
		if (stack.isEmpty())
			return result;
		else {
			// 利用递归函数得到最后一个元素
			T last = getAndRemoveLast(stack);
			// 将当前弹出的元素压回栈中
			stack.push(result);
			return last;
		}
	}

	/**
	 * 将一个栈逆序
	 * 
	 * @param stack
	 */
	public static <T> void reverse(Stack<T> stack) {
		if (stack.isEmpty()) {
			// 栈为空，返回
			return;
		}
		// 得到栈的栈底并移除
		T last = getAndRemoveLast(stack);
		// 将其他元素逆序
		reverse(stack);
		// 将栈底压入栈
		stack.push(last);
	}
}
